testdome Python Interview questions¶
1. File Owners¶
Implement a group_by_owners function
def group_by_owners(files):
res = {}
for k,v in files.items():
if v in res:
res[v].append(k)
else:
res[v] = [k]
return res
files = {
'Input.txt': 'Randy',
'Code.py': 'Stan',
'Output.txt': 'Randy'
}
print(group_by_owners(files))
# {'Randy': ['Input.txt', 'Output.txt'], 'Stan': ['Code.py']}
2. Ice Cream Machine¶
Implement the IceCreamMachine’s scoops method so that it returns
all combinations of one ingredient and one topping.
If there are no ingredients or toppings, the method
should return an empty list.
For example:
IceCreamMachine([“vanilla”, “chocolate”], [“chocolate sauce”]).scoops()
should return
[[‘vanilla’, ‘chocolate sauce’], [‘chocolate’, ‘chocolate sauce’]].
class IceCreamMachine:
def __init__(self, ingredients, toppings):
self.ingredients = ingredients
self.toppings = toppings
def scoops(self):
res = []
for ing in self.ingredients:
for top in self.toppings:
res.append([ing, top])
return res
machine = IceCreamMachine(["vanilla", "chocolate"], ["chocolate sauce"])
print(machine.scoops())
# [['vanilla', 'chocolate sauce'], ['chocolate', 'chocolate sauce']]
3. Merge Names¶
Implement the unique_names method.
When passed two arrays of names, it will return an array containing
the names that appear in either or both arrays.
The returned array should have no duplicates.
For example, calling unique_names
([‘Ava’, ‘Emma’, ‘Olivia’], [‘Olivia’, ‘Sophia’, ‘Emma’])
should return an array containing
Ava, Emma, Olivia, and Sophia
in any order.
def unique_names(names1, names2):
return list(set(names1 + names2))
names1 = ["Ava", "Emma", "Olivia"]
names2 = ["Olivia", "Sophia", "Emma"]
print(unique_names(names1, names2))
# Ava, Emma, Olivia, Sophia
4. Palindrome¶
A Palindrome is a word that reads the same backward or forward.
Write a function that checks if a given word is a palindrome.
Character case should be ignored.
For example:
is_palindrome(“Deleveled”)
should return
True
as character case should be ignored, resulting in “deleveled”,
which is a palindrome since it reads the same backward and forward.
def is_palindrome(word):
return all(word[i].lower() == word[len(word) - i - 1].lower() for i in range(len(word)//2))
from collections import deque
def is_palindrome_01(s):
q = deque(s)
return all(q.popleft().lower() == q.pop().lower() for i in range(len(s) // 2))
print(is_palindrome('Deleveled'))
print(is_palindrome_01('Deleveled'))
5. Binary Search Tree [BST]¶
A three-node binary tree.
Binary search tree (BST) is a binary tree where the value of each node
is larger or equal to the values in all the nodes in that node’s left
subtree and is smaller than the values in all the nodes in that node’s
right subtree.
Write a function that, efficiently with respect to time used,
checks if a given binary search tree contains a given value.
For example, for the following tree:
n1 (Value: 1, Left: null, Right: null)
n2 (Value: 2, Left: n1, Right: n3)
n3 (Value: 3, Left: null, Right: null)
Call to contains(n2, 3) should return
True
since a tree with root at n2 contains number 3.
import collections
Node = collections.namedtuple('Node', ['left', 'right', 'value'])
def contains(root, value):
if root:
if root.value == value:
return True
elif root.value > value:
return contains(root.left, value)
else:
return contains(root.right, value)
return False
n1 = Node(value=1, left=None, right=None)
n3 = Node(value=3, left=None, right=None)
n2 = Node(value=2, left=n1, right=n3)
print(contains(n2, 3))
# Root: Node(left=Node(left=None, right=None, value=1), \
# right=Node(left=None, right=None, value=3), \
# value=2)
# Root: Node(left=None, right=None, value=1)
# Root: Node(left=None, right=None, value=3)
# True
Hint 1:
The easiest way to navigate a binary search tree is using recursion.
Return value in root.left or value in root.right
6. Song¶
A playlist is considered a repeating playlist if any of the songs
contain a reference to a previous song in the playlist.
Otherwise, the playlist will end with the last song which points to None.
Implement a function is_repeating_playlist that, efficiently with respect
to time used, returns true if a playlist is repeating or false if it is not.
For example, the following code prints “True” as both songs point to each other.
class Song:
songs = []
def __init__(self, name):
self.name = name
self.next = None
Song.songs.append(name)
def next_song(self, song):
self.next = song
Song.songs.append(song.name)
def is_repeating_playlist(self):
"""
:returns: (bool) True if the playlist is repeating, False if not.
"""
return self.name in Song.songs
first = Song("Hello")
print("First:", first.songs)
second = Song("Eye of the tiger")
print("Second: ", second.songs)
print("First:", first.songs)
first.next_song(second);
second.next_song(first);
print("First:", first.songs)
print("Second: ", second.songs)
print(first.is_repeating_playlist())
# True
Hint 1:
A data structure can be used to identify if a song appears twice in a playlist.
7. Two Sum¶
Write a function that, when passed a list and a target sum, returns,
EFFICIENTLY with respect to time used, two distinct zero-based indices
of any two of the numbers, whose sum is equal to the target sum.
If there are no two numbers, the function should return None.
For example:
find_two_sum([3, 1, 5, 7, 5, 9], 10)
should return a single tuple containing any of the following pairs of indices:
0 and 3 (or 3 and 0) as 3 + 7 = 10
1 and 5 (or 5 and 1) as 1 + 9 = 10
2 and 4 (or 4 and 2) as 5 + 5 = 10
def find_two_sum(numbers, target_sum):
"""
:param numbers: (list of ints) The list of numbers.
:param target_sum: (int) The required target sum.
:returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
"""
return None
print(find_two_sum([3, 1, 5, 7, 5, 9], 10))
Brute force solution. The time complexity is O(N^2)
def find_two_sum(numbers, target_sum):
"""
:param numbers: (list of ints) The list of numbers.
:param target_sum: (int) The required target sum.
:returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
"""
pairs = []
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if int(numbers[i]) + int(numbers[j]) == target_sum:
# pairs.append(str(i) + " and " + str(j))
return i, j
return None
print(find_two_sum([3, 1, 5, 7, 5, 9], 10))
# (0,3)
Hint 1:
Nested for loops can iterate over the list and calculate a sum in O(N^2) time.
Using binary search. The time complexity is O(N*logN)
def find_two_sum(numbers, target_sum):
"""
:param numbers: (list of ints) The list of numbers.
:param target_sum: (int) The required target sum.
:returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
"""
sort_numbers = sorted(numbers) # O(logN)
i = 0
j = len(sort_numbers) - 1
while True:
if i > j:
return None
curr_summ = sort_numbers[i] + sort_numbers[j]
if curr_summ == target_sum:
return numbers.index(sort_numbers[i]), numbers.index(sort_numbers[j]) # O(n) + O(n)
elif curr_summ > target_sum:
j -= 1
else:
i += 1
print(find_two_sum([3, 1, 5, 7, 5, 9], 10))
Using Hash
Base on [2] algorithm and use hash, the time complexity can be reduced to O(N),
but this solution will add the O(N) space of hash.
Optimal algorithm:
Pseduo-code:
for (i=0; j=n-1; i<j)
if arr[i] + arr[j] == sum
return (i,j)
elif arr[i]+arr[j] < sum
i++;
else
j–
return(-1,-1);
or
If a[M] + a[m] > I then M–
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.
8. Pipeline¶
As part of a data processing pipeline, complete the implementation
of the pipeline method:
The method should accept a variable number of functions, and it should return
a new function that accepts one parameter arg.
The returned function should call the first function in the pipeline
with the parameter arg, and call the second function with the result
of the first function.
The returned function should continue calling each function in the
pipeline in order, following the same pattern, and return the value
from the last function.
For example,
pipeline(lambda x: x * 3, lambda x: x + 1, lambda x: x / 2)
then calling the returned function with 3 should return 5.0.
def pipeline(*funcs):
def helper(arg):
res = arg
for f in funcs:
res = f(res)
print(res)
return res
return helper
fun = pipeline(lambda x: x * 3, lambda x: x + 1, lambda x: x / 2)
print(fun(3)) #should print 5.0
9. League Table¶
The LeagueTable class tracks the score of each player in a league.
After each game, the player records their score with the record_result function.
The player’s rank in the league is calculated using the following logic:
- The player with the highest score is ranked first (rank 1).
The player with the lowest score is ranked last.
- If two players are tied on score, then the player who has played the
fewest games is ranked higher.
- If two players are tied on score and number of games played, then the
player who was first in the list of players is ranked higher.
Implement the player_rank function that returns the player at the given rank.
For example:
table = LeagueTable([‘Mike’, ‘Chris’, ‘Arnold’])
table.record_result(‘Mike’, 2)
table.record_result(‘Mike’, 3)
table.record_result(‘Arnold’, 5)
table.record_result(‘Chris’, 5)
print(table.player_rank(1))
All players have the same score.
However, Arnold and Chris have played fewer games than Mike,
and as Chris is before Arnold in the list of players, he is ranked first.
Therefore, the code above should display
“Chris”.
from collections import Counter
from collections import OrderedDict
class LeagueTable:
def __init__(self, players):
self.standings = OrderedDict([(player, Counter()) for player in players])
def record_result(self, player, score):
self.standings[player]['games_played'] += 1
self.standings[player]['score'] += score
def player_rank(self, rank):
print(self.standings)
for player in self.standings:
if self.standings[player]['games_played'] == rank:
return player
table = LeagueTable(['Mike', 'Chris', 'Arnold'])
table.record_result('Mike', 2)
table.record_result('Mike', 3)
table.record_result('Arnold', 5)
table.record_result('Chris', 5)
print(table.player_rank(1))
10. Path¶
Write a function that provides change directory (cd) function for an abstract file system.
Notes:
Root path is ‘/’.
Path separator is ‘/’.
Parent directory is addressable as ‘..’.
Directory names consist only of English alphabet letters (A-Z and a-z).
The function should support both relative and absolute paths.
The function will not be passed any invalid paths.
Do not use built-in path-related functions.
For example:
class Path:
def __init__(self, path):
self.current_path = path
def cd(self, new_path):
pass
class Path:
def __init__(self, path):
self.current_path = path
def cd(self, new_path):
old_path = self.current_path.split('/')
new_path = new_path.split('/')
print(old_path)
print(new_path)
chunks_cnt = 0
for chunk in new_path:
if chunk == "..":
chunks_cnt += 1
str_out = ""
for i in range(len(old_path) - chunks_cnt):
str_out += old_path[i] + "/"
for i in range(len(new_path)):
if new_path[i] != "..":
str_out += new_path[i] + "/"
current_path = str_out[:len(str_out) - 1]
self.current_path = current_path
# return current_path
path = Path('/a/b/c/d')
path.cd('../x')
print(path.current_path)
# should display '/a/b/c/x'.